package org.algorithm.biubiu.wheel_1.回溯算法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *给定一个候选人编号的集合candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
 *
 * candidates中的每个数字在每个组合中只能使用一次。
 *
 * 注意：解集不能包含重复的组合。
 *
 * 40. 组合总和 II
 *
 * 链接：https://leetcode-cn.com/problems/combination-sum-ii
 */
public class $4月22日$组合总和2 {


  class Solution {
    List<List<Integer>> res = new ArrayList();
   int[] arr;
   int target;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        this.arr = candidates;
        this.target= target;
        Arrays.sort(arr);
        backtrack(0,0);
        return res;
    }

    List<Integer> cur = new ArrayList();
  
    public void backtrack(int index,int sum){
         if(sum==target){
             res.add(new ArrayList(cur));
             return;
         }

         for(int i= index;i<arr.length;i++){
             if(i>index && arr[i]==arr[i-1]){
                 continue;
             }
             if(sum+arr[i]<=target){
                 cur.add(arr[i]);
                 backtrack(i+1,sum+arr[i]);
                cur.remove(cur.size()-1);
             }
            
         }
    }
}
}
